public class QuickSort {
    public static int[] arr = {4,9,5,6,7,1,2,8,3};
    public static int n = arr.length;
    public static void main(String[] args) {
        quickSort2(0,n-1);
        for(int e : arr){
            System.out.print(e + " ");
        }
    }


    //随机快速排序经典写法
    public static void quickSort1(int l,int r) {
        if(l >= r) {
            return;
        }
        //随机获取
        int x = arr[l + (int) Math.random()*(r - l +1)];
        int mid = partition1(l,r,x);
        quickSort1(l,mid-1);
        quickSort1(mid+1,r);
    }

    public static int partition1(int l, int r, int x) {
        int a = l;
        int xi = -1;//记录x所在的位置
        for(int i = l; i<= r ; ++i) {
            if(arr[i] <= x){
                swap(a,i);
                a++;
                if(arr[i] == x){
                    xi = i;
                }
            }
        }
        swap(a-1,xi);
        return a-1;
    }


    //快排荷兰国旗问题
    public static void quickSort2(int l,int r) {
        if(l >= r) {
            return;
        }
        //随机获取
        int x = arr[l + (int) Math.random()*(r - l +1)];
        int[] range = partition2(l,r,x);
        int left = range[0];
        int right = range[1];
        quickSort1(l,left);
        quickSort1(right,r);
    }

    public static int[] partition2(int l, int r, int x) {
        int a = l;  //小于x的左部位置
        int b = r;  //大于x的右部位置
        int i = l;
        while(i<=b) {
            if(arr[i] < x) {
                swap(a,i);
                a++;
                i++;
            }
            else if(arr[i] > x) {
                swap(b,i);
                b--;
            }
            else {
                i++;
            }
        }
        int ret[]  ={a-1,b+1};
        return ret;
    }

    public static void swap(int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
